{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Graph Valid Tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #depth-first-search #breadth-first-search #union-find #graph"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #深度优先搜索 #广度优先搜索 #并查集 #图"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: validTree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #以图判树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定编号从 <code>0</code> 到 <code>n - 1</code>&nbsp;的&nbsp;<code>n</code> 个结点。给定一个整数&nbsp;<code>n</code>&nbsp;和一个&nbsp;<code>edges</code>&nbsp;列表，其中&nbsp;<code>edges[i] = [a<sub>i</sub>, b<sub>i</sub>]</code>&nbsp;表示图中节点&nbsp;<code>a<sub>i</sub></code>&nbsp;和&nbsp;<code>b<sub>i</sub></code>&nbsp;之间存在一条无向边。</p>\n",
    "\n",
    "<p>如果这些边能够形成一个合法有效的树结构，则返回 <code>true</code> ，否则返回 <code>false</code> 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img src=\"https://assets.leetcode.com/uploads/2021/03/12/tree1-graph.jpg\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> <code>n = 5</code>, edges<code> = [[0,1],[0,2],[0,3],[1,4]]</code>\n",
    "<strong>输出:</strong> true</pre>\n",
    "\n",
    "<p><strong>示例 2:</strong></p>\n",
    "\n",
    "<p><img src=\"https://assets.leetcode.com/uploads/2021/03/12/tree2-graph.jpg\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> <code>n = 5, </code>edges<code> = [[0,1],[1,2],[2,3],[1,3],[1,4]]</code>\n",
    "<strong>输出:</strong> false</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= n &lt;= 2000</code></li>\n",
    "\t<li><code>0 &lt;= edges.length &lt;= 5000</code></li>\n",
    "\t<li><code>edges[i].length == 2</code></li>\n",
    "\t<li><code>0 &lt;= a<sub>i</sub>, b<sub>i</sub>&nbsp;&lt; n</code></li>\n",
    "\t<li><code>a<sub>i</sub>&nbsp;!= b<sub>i</sub></code></li>\n",
    "\t<li>不存在自循环或重复的边</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [graph-valid-tree](https://leetcode.cn/problems/graph-valid-tree/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [graph-valid-tree](https://leetcode.cn/problems/graph-valid-tree/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['5\\n[[0,1],[0,2],[0,3],[1,4]]', '5\\n[[0,1],[1,2],[2,3],[1,3],[1,4]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UF:\n",
    "    def __init__(self, n):\n",
    "        self.count = n\n",
    "        self.parent = [i for i in range(n)]\n",
    "    \n",
    "    def find(self, x):\n",
    "        if self.parent[x] != x:\n",
    "            self.parent[x] = self.find(self.parent[x])\n",
    "        return self.parent[x]\n",
    "\n",
    "    def union(self, p, q):\n",
    "        rootP = self.find(p)\n",
    "        rootQ = self.find(q)\n",
    "\n",
    "        if rootP == rootQ:\n",
    "            return False\n",
    "        \n",
    "        self.parent[rootQ] = rootP\n",
    "        self.count -= 1\n",
    "        return True\n",
    "        \n",
    "\n",
    "class Solution:\n",
    "    def validTree(self, n: int, edges: List[List[int]]) -> bool:\n",
    "        uf = UF(n)\n",
    "        for e in edges:\n",
    "            unique = uf.union(e[0],e[1])\n",
    "            if not unique: return False\n",
    "        return uf.count == 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validTree(self, n: int, edges: List[List[int]]) -> bool:\n",
    "        # 本质上是最小生成树算法的衍生，主要考察构成树的过程中有没有环\n",
    "        # 思路是不断地增加边，并且增加之前判断这条边上的两个节点是否联通，如果联通，那就说明成环了，返回False\n",
    "        uf = UF(n)\n",
    "        res = True\n",
    "        for edge in edges:\n",
    "            if not uf.connected(edge[0], edge[1]):\n",
    "                uf.union(edge[0], edge[1])\n",
    "            else:\n",
    "                res = False\n",
    "        if uf.count != 1:\n",
    "            return False\n",
    "        return res\n",
    "\n",
    "class UF:\n",
    "    # n 为图中节点的个数\n",
    "    def __init__(self, n: int):\n",
    "        self.count = n\n",
    "        self.parent = [i for i in range(n)]\n",
    "\n",
    "    # 将节点 p 和节点 q 连通\n",
    "    def union(self, p: int, q: int):\n",
    "        rootP = self.find(p)\n",
    "        rootQ = self.find(q)\n",
    "        if rootP == rootQ:\n",
    "            return\n",
    "\n",
    "        self.parent[rootQ] = rootP\n",
    "        # 两个连通分量合并成一个连通分量\n",
    "        self.count -= 1\n",
    "\n",
    "    # 判断节点 p 和节点 q 是否连通\n",
    "    def connected(self, p: int, q: int) -> bool:\n",
    "        rootP = self.find(p)\n",
    "        rootQ = self.find(q)\n",
    "        return rootP == rootQ\n",
    "\n",
    "    def find(self, x: int) -> int:\n",
    "        if self.parent[x] != x:\n",
    "            self.parent[x] = self.find(self.parent[x])\n",
    "        return self.parent[x]\n",
    "\n",
    "    # 返回图中的连通分量个数\n",
    "    def count(self) -> int:\n",
    "        return self.count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validTree(self, n: int, edges: List[List[int]]) -> bool:\n",
    "        if not n:\n",
    "            return True\n",
    "\n",
    "        uf = UF(n)\n",
    "        for i, j in edges:\n",
    "            if uf.connected(i, j):  # If already connected, it's a cycle\n",
    "                return False\n",
    "            uf.union(i, j)\n",
    "\n",
    "        return uf.getCount() == 1 \n",
    "\n",
    "class UF:\n",
    "    def __init__(self, n: int):\n",
    "        self.count = n\n",
    "        self.parents = [i for i in range(n)]\n",
    "    \n",
    "    def find(self, i: int):\n",
    "        while self.parents[i] != i:\n",
    "            i = self.parents[i]\n",
    "        return i \n",
    "    \n",
    "    def connected(self, i: int, j: int) -> bool:\n",
    "        return self.find(i) == self.find(j)\n",
    "    \n",
    "    def union(self, i: int, j: int) -> bool:\n",
    "        rootI = self.find(i)\n",
    "        rootJ = self.find(j)\n",
    "        if rootI == rootJ:\n",
    "            return False \n",
    "        self.parents[rootI] = rootJ\n",
    "        self.count -= 1 \n",
    "        return True\n",
    "    \n",
    "    def getCount(self):\n",
    "        return self.count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validTree(self, n: int, edges: List[List[int]]) -> bool:\n",
    "        if not n:\n",
    "            return True\n",
    "\n",
    "        uf = UF(n)\n",
    "        for i, j in edges:\n",
    "            if uf.connected(i, j):  # If already connected, it's a cycle\n",
    "                return False\n",
    "            uf.union(i, j)\n",
    "\n",
    "        return uf.getCount() == 1 \n",
    "\n",
    "class UF:\n",
    "    def __init__(self, n: int):\n",
    "        self.count = n\n",
    "        self.parents = [i for i in range(n)]\n",
    "    \n",
    "    def find(self, i: int):\n",
    "        while self.parents[i] != i:\n",
    "            self.parents[i] = self.parents[self.parents[i]]\n",
    "            i = self.parents[i]\n",
    "        return i \n",
    "    \n",
    "    def connected(self, i: int, j: int) -> bool:\n",
    "        return self.find(i) == self.find(j)\n",
    "    \n",
    "    def union(self, i: int, j: int) -> bool:\n",
    "        rootI = self.find(i)\n",
    "        rootJ = self.find(j)\n",
    "        if rootI == rootJ:\n",
    "            return False \n",
    "        self.parents[rootI] = rootJ\n",
    "        self.count -= 1 \n",
    "        return True\n",
    "    \n",
    "    def getCount(self):\n",
    "        return self.count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validTree(self, n: int, edges: List[List[int]]) -> bool:\n",
    "        m=len(edges)\n",
    "        if m!=n-1:\n",
    "            return False\n",
    "        adj=defaultdict(list)\n",
    "        for a,b in edges:\n",
    "            adj[a].append(b)\n",
    "            adj[b].append(a)\n",
    "        visit=[0]*n\n",
    "        visit[0]=1\n",
    "        bfs=[0]\n",
    "        while bfs:\n",
    "            nbfs=[]\n",
    "            for p in bfs:\n",
    "                for con in adj[p]:\n",
    "                    if visit[con]==0:                        \n",
    "                        visit[con]=1\n",
    "                        nbfs.append(con) \n",
    "\n",
    "            bfs=nbfs\n",
    "       \n",
    "        return sum(visit)==n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind:\n",
    "\n",
    "    def __init__(self, n):\n",
    "        self.parent = [node for node in range(n)]\n",
    "    \n",
    "    def find(self, A):\n",
    "        while A != self.parent[A]:\n",
    "            A = self.parent[A]\n",
    "        return A\n",
    "    \n",
    "    def union(self, A, B):\n",
    "        root_A = self.find(A)\n",
    "        root_B = self.find(B)\n",
    "\n",
    "        if root_A == root_B:\n",
    "            return False\n",
    "            \n",
    "        self.parent[root_A] = root_B\n",
    "        return True \n",
    "\n",
    "class Solution:\n",
    "    def validTree(self, n: int, edges: List[List[int]]) -> bool:\n",
    "        \n",
    "        if len(edges) != n - 1:\n",
    "            return False\n",
    "        \n",
    "        union_find = UnionFind(n)\n",
    "\n",
    "        for A, B in edges:\n",
    "            if not union_find.union(A, B):\n",
    "                return False\n",
    "        \n",
    "        return True \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Union_find:\n",
    "    def __init__(self, n):\n",
    "        self.parent = [i for i in range(n)]\n",
    "        self.size = [1] * n\n",
    "        self.count = n\n",
    "    \n",
    "    def find(self, a):\n",
    "        while a != self.parent[a]:\n",
    "            self.parent[a] = self.parent[self.parent[a]]\n",
    "            a = self.parent[a]\n",
    "        return a\n",
    "    \n",
    "    def union(self, a, b):\n",
    "        pa = self.parent[a]\n",
    "        pb = self.parent[b]\n",
    "        if pa == pb:\n",
    "            return \n",
    "        \n",
    "        if self.size[pa] < self.size[pb]:\n",
    "            self.parent[pa] = pb\n",
    "            self.size[pb] += self.size[pa]\n",
    "        else:\n",
    "            self.parent[pb] = pa\n",
    "            self.size[pa] += self.size[pb]\n",
    "        self.count -= 1\n",
    "    \n",
    "    def connect(self, a, b):\n",
    "        return self.find(a) == self.find(b)\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def validTree(self, n: int, edges: List[List[int]]) -> bool:\n",
    "        uf = Union_find(n)\n",
    "        for e in edges:\n",
    "            if uf.connect(e[0], e[1]):\n",
    "                return False\n",
    "            else:\n",
    "                uf.union(e[0], e[1])\n",
    "        return uf.count == 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validTree(self, n: int, edges: List[List[int]]) -> bool:\n",
    "        m=len(edges)\n",
    "        if m!=n-1:\n",
    "            return False\n",
    "        adj=defaultdict(list)\n",
    "        for a,b in edges:\n",
    "            adj[a].append(b)\n",
    "            adj[b].append(a)\n",
    "        visit=[0]*n\n",
    "        visit[0]=1\n",
    "        dfs=[0]\n",
    "        while dfs:\n",
    "            p=dfs.pop()\n",
    "          \n",
    "            for con in adj[p]:\n",
    "                if visit[con]==0:                        \n",
    "                    visit[con]=1\n",
    "                    dfs.append(con) \n",
    "\n",
    "           \n",
    "       \n",
    "        return sum(visit)==n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validTree(self, n: int, edges: List[List[int]]) -> bool:\n",
    "        ld=[0]*n\n",
    "        adj=defaultdict(list)\n",
    "        for a,b in edges:\n",
    "            adj[a].append(b)\n",
    "            adj[b].append(a)\n",
    "            ld[a]+=1\n",
    "            ld[b]+=1\n",
    "        m=len(edges)\n",
    "        if m!=n-1:\n",
    "            return False\n",
    "\n",
    "\n",
    "        leave=[]\n",
    "        for i in range(n):\n",
    "            if ld[i]==1:\n",
    "                leave.append(i)\n",
    "           \n",
    "        # print(leave)\n",
    "        while leave:\n",
    "            l=leave.pop()\n",
    "            if ld[l]==1:\n",
    "                ld[l]-=1\n",
    "                for con in adj[l]:\n",
    "                    if ld[con]>0:\n",
    "                        ld[con]-=1\n",
    "                        if ld[con]==1:\n",
    "                            leave.append(con)\n",
    "        # print(ld)\n",
    "        if sum(ld)==0:\n",
    "            return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validTree(self, n: int, edges: List[List[int]]) -> bool:\n",
    "        visited = [0 for i in range(n)]\n",
    "        adj = [[] for i in range(n)]\n",
    "        for e in edges:\n",
    "            adj[e[0]].append(e[1])\n",
    "            adj[e[1]].append(e[0])\n",
    "        stack = [0]\n",
    "\n",
    "        parent = [i for i in range(n)]\n",
    "        while len(stack) > 0:\n",
    "            v = stack.pop()\n",
    "            visited[v] = -1\n",
    "            for u in adj[v]:\n",
    "                parent[u] = v\n",
    "                if visited[u] == -1 and parent[v] != u:\n",
    "                    return False\n",
    "                if visited[u] == 0:\n",
    "                    stack.append(u)\n",
    "            # visited[v] = 1\n",
    "        for i in range(n):\n",
    "            if visited[i] == 0:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validTree(self, n: int, edges: List[List[int]]) -> bool:\n",
    "        m=len(edges)\n",
    "        if m!=n-1:\n",
    "            return False\n",
    "        ld=[0]*n\n",
    "        adj=defaultdict(list)\n",
    "        for a,b in edges:\n",
    "            adj[a].append(b)\n",
    "            adj[b].append(a)\n",
    "            ld[a]+=1\n",
    "            ld[b]+=1\n",
    "       \n",
    "\n",
    "\n",
    "        leave=[]\n",
    "        for i in range(n):\n",
    "            if ld[i]==1:\n",
    "                leave.append(i)\n",
    "           \n",
    "        # print(leave)\n",
    "        while leave:\n",
    "            l=leave.pop()\n",
    "            if ld[l]==1:\n",
    "                ld[l]-=1\n",
    "                for con in adj[l]:\n",
    "                    if ld[con]>0:\n",
    "                        ld[con]-=1\n",
    "                        if ld[con]==1:\n",
    "                            leave.append(con)\n",
    "        # print(ld)\n",
    "        if sum(ld)==0:\n",
    "            return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validTree(self, n: int, edges: List[List[int]]) -> bool:\n",
    "        uf = UF(n) \n",
    "        ans = True\n",
    "        for e in edges:\n",
    "            u, v = e[0], e[1]\n",
    "            if uf.connected(u, v):\n",
    "                ans = False  \n",
    "            uf.union(u, v)\n",
    "        if ans == False:\n",
    "            return ans \n",
    "        else:\n",
    "            if uf.count > 1:\n",
    "                return False \n",
    "            else:\n",
    "                return True\n",
    "    \n",
    "\n",
    "\n",
    "\n",
    "class UF:\n",
    "    def __init__(self, n):\n",
    "        self.count = n\n",
    "        self.parent = [i for i in range(n)]\n",
    "        self.size = [1]*n  \n",
    "    \n",
    "    def find(self, p):\n",
    "        while p!=self.parent[p]:\n",
    "            self.parent[p] = self.find(self.parent[p])\n",
    "            p = self.parent[p] \n",
    "        return p \n",
    "\n",
    "    def union(self, p, q):\n",
    "        rootP, rootQ = self.find(p), self.find(q)\n",
    "        if rootP == rootQ:\n",
    "            return \n",
    "        \n",
    "        if self.size[rootP]<self.size[rootQ]:\n",
    "            self.parent[rootP] = rootQ \n",
    "            self.size[rootQ]+=self.size[rootP]\n",
    "        else:\n",
    "            self.parent[rootQ] = rootP \n",
    "            self.size[rootP] += self.size[rootQ]\n",
    "        \n",
    "        self.count-=1 \n",
    "    \n",
    "    def connected(self, p, q):\n",
    "        rootP, rootQ = self.find(p), self.find(q) \n",
    "        return rootP == rootQ"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validTree(self, n: int, edges: List[List[int]]) -> bool:\n",
    "        if len(edges) != n - 1: \n",
    "            return False\n",
    "        \n",
    "        adj_list = {i: [] for i in range(n)}\n",
    "        for A, B in edges:\n",
    "            adj_list[A].append(B)\n",
    "            adj_list[B].append(A)\n",
    "        \n",
    "        parent = {0: -1}\n",
    "        queue = collections.deque([0])\n",
    "        \n",
    "        while queue:\n",
    "            node = queue.popleft()\n",
    "            for neighbour in adj_list[node]:\n",
    "                if neighbour == parent[node]:\n",
    "                    continue\n",
    "                if neighbour in parent:\n",
    "                    return False\n",
    "                parent[neighbour] = node\n",
    "                queue.append(neighbour)\n",
    "        \n",
    "        return len(parent) == n\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "这个问题要求我们根据给定的节点数（n）和边（edges）判断这个图是不是tree (目的是检测是否存在环)\n",
    "构建graph, bfs遍历图，如果所有的节点都被访问一次，就是树\n",
    "\n",
    "创建一个graph, 无向图\n",
    "{0: [1, 2, 3], 1: [0, 4], 2: [0], 3: [0], 4: [1]})\n",
    "\n",
    "使用bfs检查这个graph, 在queue中存（node, parent)\n",
    "\n",
    "为什么在queue中存 (node, parent): 如果我们从A节点访问B节点，我们不希望下一步访问B节点的邻居节点时再访问A节点。\n",
    "为什么用visited: 检测图中是否存在环, 在bfs过程中，如果我们访问到一个已经访问过的节点，那么就意味着图中存在环。\n",
    "\n",
    "从树的根节点开始，遍历这个树，如果所有的点都遍历到了(存在一个联通块)并且没有重复访问一个节点，说明是一个树\n",
    "\n",
    "比如0可以访问到2，当我到4的时候，2已经访问过了，如果我可以从4访问到2，说明存在Cycle，就不是树\n",
    "跟踪parent的目的就是为了在遍历时避免将父节点再次访问，从而避免错误地检测到环\n",
    "\"\"\"\n",
    "from collections import defaultdict, deque\n",
    "\n",
    "class Solution:\n",
    "    def validTree(self, n: int, edges: List[List[int]]) -> bool:\n",
    "        graph = defaultdict(list)\n",
    "\n",
    "        for x, y in edges:\n",
    "            graph[x].append(y)\n",
    "            graph[y].append(x)\n",
    "\n",
    "        queue = deque([0])\n",
    "        visited = set()\n",
    "\n",
    "        while queue:\n",
    "            node = queue.popleft()\n",
    "\n",
    "            # 重复访问一个node,说明有环，不可能是树\n",
    "            if node in visited:\n",
    "                return False\n",
    "\n",
    "            # 第一次访问到放入visited, 然后把当前node的子节点放入queue\n",
    "            visited.add(node)\n",
    "            for neighbor in graph[node]:\n",
    "                if neighbor in visited:\n",
    "                    continue\n",
    "                queue.append(neighbor)\n",
    "        \n",
    "        return len(visited) == n\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validTree(self, n: int, edges: List[List[int]]) -> bool:\n",
    "        visited = {0}\n",
    "        # edgeSet = set()\n",
    "        edges = [tuple(sorted(e)) for e in edges]\n",
    "        edges.sort()\n",
    "        edges = set(edges)\n",
    "        q = [0]\n",
    "        while q:\n",
    "            curr = q.pop(0)\n",
    "            for j in range(n):\n",
    "                if (curr, j) in edges or (j, curr) in edges:\n",
    "                    if (curr, j) in edges:\n",
    "                        edges.remove((curr, j))\n",
    "                    else:\n",
    "                        edges.remove((j, curr))\n",
    "                    if j not in visited:\n",
    "                        q.append(j)\n",
    "                        visited.add(j)\n",
    "                    else:\n",
    "                        return False\n",
    "        if len(visited) == n:\n",
    "            return True\n",
    "        else:\n",
    "            return False\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def helper(self, n, edges):\n",
    "        graph = [[] for _ in range(n)]\n",
    "        for i in edges:\n",
    "            graph[i[0]].append(i[1])\n",
    "            graph[i[1]].append(i[0])\n",
    "\n",
    "        print(graph)\n",
    "        visited = [False for _ in range(n)]\n",
    "        q = deque()\n",
    "        q.append(0)\n",
    "        visited[0] = True \n",
    "        count = 0\n",
    "\n",
    "        while q:\n",
    "            cur = q.popleft()\n",
    "            count += 1 \n",
    "            for i in graph[cur]:\n",
    "                if not visited[i]:\n",
    "                    q.append(i)\n",
    "                    visited[i] = True\n",
    "        print(count)\n",
    "\n",
    "        return False if count != n else True\n",
    "\n",
    "    def validTree(self, n: int, edges: List[List[int]]) -> bool:\n",
    "        is_connected = self.helper(n, edges)\n",
    "        if n > len(edges) and is_connected:\n",
    "            return True \n",
    "        else:\n",
    "            return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validTree(self, n: int, edges: List[List[int]]) -> bool:\n",
    "        if len(edges) == 0:\n",
    "            return n == 1\n",
    "        parent = [-1]*n\n",
    "        adjDict = {i: [] for i in range(n)}\n",
    "        adjCnt = {i: 0 for i in range(n)}\n",
    "        root = edges[0][0]\n",
    "        noneEmpty = 0\n",
    "        \n",
    "        def couterDegree(u):\n",
    "            nonlocal adjCnt, noneEmpty\n",
    "            adjCnt[u] += 1\n",
    "            if adjCnt[u] == 1:\n",
    "                noneEmpty += 1\n",
    "        \n",
    "        for u, v in edges:\n",
    "            couterDegree(u)\n",
    "            couterDegree(v)\n",
    "        if noneEmpty != n:\n",
    "            return False \n",
    "        \n",
    "        for u, v in edges:\n",
    "            adjDict[u].append(v)\n",
    "            adjDict[v].append(u)\n",
    "\n",
    "        def dfs_find_compact(child) -> int:\n",
    "            if parent[child] == -1:\n",
    "                return child\n",
    "            r = dfs_find_compact(parent[child])\n",
    "            parent[child] = r \n",
    "            return r\n",
    "        \n",
    "        nextnodes = [root]\n",
    "\n",
    "        visited = set()\n",
    "        while len(nextnodes) > 0:\n",
    "            pre = nextnodes[0]\n",
    "            visited.add(pre)\n",
    "            nextnodes = nextnodes[1:]\n",
    "            r0 = dfs_find_compact(pre)\n",
    "            for c in adjDict[pre]:\n",
    "                if c in visited:\n",
    "                    continue\n",
    "\n",
    "                r = dfs_find_compact(c)\n",
    "                if r0 == r:\n",
    "                    return False\n",
    "                parent[c] = pre\n",
    "                \n",
    "                nextnodes.append(c)\n",
    "\n",
    "        return len(visited) == n\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validTree(self, n: int, edges: List[List[int]]) -> bool:\n",
    "        node_dict = collections.defaultdict(set)\n",
    "        for edge in edges:\n",
    "            node_dict[edge[0]].add(edge[1])\n",
    "            node_dict[edge[1]].add(edge[0])\n",
    "        visited = [False] * n\n",
    "        q = [0]\n",
    "        while q:\n",
    "            root = q.pop(0)\n",
    "            if visited[root]:\n",
    "                return False\n",
    "            else:\n",
    "                visited[root] = True\n",
    "            q += list(node_dict[root])\n",
    "            for node in node_dict[root]:\n",
    "                node_dict[node].remove(root)\n",
    "        return sum(visited) == len(visited)\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "        \n",
    "                \n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validTree(self, n: int, edges: List[List[int]]) -> bool:\n",
    "        fa = [i for i in range(n)]\n",
    "        size = n\n",
    "        \n",
    "        def find(x):\n",
    "            if fa[x] != x:\n",
    "                fa[x] = find(fa[x])\n",
    "            return fa[x]\n",
    "        \n",
    "        def merge(x, y):\n",
    "            fa[find(x)] = find(y)\n",
    "        \n",
    "        def check(x, y):\n",
    "            return find(x) == find(y)\n",
    "        \n",
    "        for x, y in edges:\n",
    "            if not check(x, y):\n",
    "                merge(x, y)\n",
    "                size -= 1\n",
    "            else:\n",
    "                return False\n",
    "        return True if size == 1 else False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class unionFind:\n",
    "    def __init__(self,n):\n",
    "        self.parent = list(range(n))\n",
    "        self.rank = [0 for _ in range(n)]\n",
    "        self.part = n\n",
    "    def find(self,x):\n",
    "        if self.parent[x] != x:\n",
    "            self.parent[x] = self.find(self.parent[x])\n",
    "        return self.parent[x]\n",
    "    def union(self, x, y):\n",
    "        root_x, root_y = self.find(x), self.find(y)\n",
    "        if root_x == root_y:\n",
    "            return False\n",
    "        if self.rank[root_x] > self.rank[root_y]:\n",
    "            root_x, root_y = root_y, root_x\n",
    "        self.parent[root_x] = root_y\n",
    "        self.rank[root_y] += self.rank[root_x]\n",
    "        self.part-=1\n",
    "        return True\n",
    "class Solution:\n",
    "    def validTree(self, n: int, edges: List[List[int]]) -> bool:\n",
    "        UF = unionFind(n)\n",
    "        for a,b in edges:\n",
    "            if not UF.union(a, b):\n",
    "                # print(a,b)\n",
    "                return False\n",
    "        if UF.part == 1:\n",
    "            return True\n",
    "        else:\n",
    "            return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validTree(self, n: int, edges: List[List[int]]) -> bool:\n",
    "        graph = defaultdict(list)\n",
    "        for e in edges:\n",
    "            s, t = e[0], e[1]\n",
    "            graph[s].append(t)\n",
    "            graph[t].append(s)\n",
    "        \n",
    "        q = deque([0])\n",
    "        visited_nodes = set([0])\n",
    "        visited_edges = set()\n",
    "        while q:\n",
    "            cur_node = q.popleft()\n",
    "            for succ in graph[cur_node]:\n",
    "                if succ not in visited_nodes:\n",
    "                    if (cur_node, succ) not in visited_edges and (succ, cur_node) not in visited_edges:\n",
    "                        q.append(succ)\n",
    "                        visited_nodes.add(succ)\n",
    "                        visited_edges.add((cur_node, succ))\n",
    "                        visited_edges.add((succ, cur_node))\n",
    "\n",
    "        if len(visited_edges) == 2*len(edges) and len(visited_nodes) == n:\n",
    "            return True\n",
    "        else:\n",
    "            return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validTree(self, n: int, edges: List[List[int]]) -> bool:\n",
    "        uf = UnionFind(n)\n",
    "        for x, y in edges:\n",
    "            if not uf.connected(x, y):\n",
    "                uf.union(x, y)\n",
    "            else:\n",
    "                return False\n",
    "        if uf.part != 1:\n",
    "            return False\n",
    "        else:\n",
    "            return True\n",
    "\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, n):\n",
    "        self.n = n\n",
    "        self.part = n\n",
    "        self.parent = [i for i in range(n)]\n",
    "        self.size = [1 for _ in range(n)]\n",
    "    def find(self, x):\n",
    "        if self.parent[x] != x:\n",
    "            self.parent[x] = self.find(self.parent[x])\n",
    "        return self.parent[x]\n",
    "    def union(self, x, y):\n",
    "        rx = self.find(x)\n",
    "        ry = self.find(y)\n",
    "        if rx == ry:\n",
    "            return\n",
    "        else:\n",
    "            self.parent[rx] = ry\n",
    "            self.size[ry] += self.size[rx]\n",
    "            self.part -= 1\n",
    "    def connected(self, x, y):\n",
    "        return self.find(x) == self.find(y)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validTree(self, n: int, edges: List[List[int]]) -> bool:\n",
    "        node_dict = collections.defaultdict(set)\n",
    "        for edge in edges:\n",
    "            node_dict[edge[0]].add(edge[1])\n",
    "            node_dict[edge[1]].add(edge[0])\n",
    "        visited = [False] * n\n",
    "        q = [0]\n",
    "        while q:\n",
    "            root = q.pop(0)\n",
    "            if visited[root]:\n",
    "                return False\n",
    "            else:\n",
    "                visited[root] = True\n",
    "            q += list(node_dict[root])\n",
    "            for node in node_dict[root]:\n",
    "                node_dict[node].remove(root)\n",
    "        out = True\n",
    "        for v in visited:\n",
    "            out &= v\n",
    "        return out\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "        \n",
    "                \n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validTree(self, n: int, edges: List[List[int]]) -> bool:\n",
    "        node_dict = collections.defaultdict(set)\n",
    "        node_in_out = collections.defaultdict(lambda:[0,0])\n",
    "        for edge in edges:\n",
    "            node_dict[edge[0]].add(edge[1])\n",
    "            node_in_out[edge[0]][1] += 1\n",
    "            node_dict[edge[1]].add(edge[0])\n",
    "            node_in_out[edge[1]][0] += 1\n",
    "        visited = [False] * n\n",
    "        root = 0\n",
    "        for node, io in node_in_out.items():\n",
    "            if io[0] == 0:\n",
    "                root = node\n",
    "                break\n",
    "        q = [root]\n",
    "        while q:\n",
    "            root = q.pop(0)\n",
    "            if visited[root]:\n",
    "                return False\n",
    "            else:\n",
    "                visited[root] = True\n",
    "            q += list(node_dict[root])\n",
    "            for node in node_dict[root]:\n",
    "                node_dict[node].remove(root)\n",
    "        out = True\n",
    "        for v in visited:\n",
    "            out &= v\n",
    "        return out\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "        \n",
    "                \n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validTree(self, n: int, edges: List[List[int]]) -> bool:\n",
    "        graph=[set() for _ in range(n)]\n",
    "        vis=[False]*n\n",
    "        for x,y in edges:\n",
    "            graph[x].add(y)\n",
    "            graph[y].add(x)\n",
    "        q=deque()\n",
    "        q.append(0)\n",
    "        while q:\n",
    "            x=q.popleft()\n",
    "            if vis[x]: return False\n",
    "            vis[x]=True\n",
    "            for y in graph[x]:\n",
    "                q.append(y)\n",
    "                graph[y].remove(x)\n",
    "        return all(vis)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # dfs + visted\n",
    "    def validTree(self, n: int, edges: List[List[int]]) -> bool:\n",
    "        en = len(edges)\n",
    "        if en != n - 1:\n",
    "            return False\n",
    "        self.adjList = [[] for _ in range(n)]\n",
    "        \n",
    "        for i in range(len(edges)):\n",
    "            self.adjList[edges[i][0]].append(edges[i][1])\n",
    "            self.adjList[edges[i][1]].append(edges[i][0])\n",
    "        \n",
    "        self.visited = [False for _ in range(n)]\n",
    "        self.dfs(0)\n",
    "        \n",
    "        for i in range(n):\n",
    "            if self.visited[i] == False:\n",
    "                return False\n",
    "        return True\n",
    "    \n",
    "    def dfs(self,index) -> bool:\n",
    "        self.visited[index] = True\n",
    "        \n",
    "        for i in self.adjList[index]:\n",
    "            if self.visited[i] == False:\n",
    "                self.dfs(i)\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validTree(self, n: int, edges: List[List[int]]) -> bool:\n",
    "        if len(edges) != n-1: return False\n",
    "        visited = [False for _ in range(n)]\n",
    "        graph = [[] for _ in range(n)]\n",
    "        for x, y in edges:\n",
    "            graph[x].append(y)\n",
    "            graph[y].append(x)\n",
    "\n",
    "        def dfs(i):\n",
    "            visited[i] = True\n",
    "            for y in graph[i]:\n",
    "                if visited[y] == False:\n",
    "                    dfs(y)\n",
    "                \n",
    "        dfs(0)\n",
    "\n",
    "        for x in range(n):\n",
    "            if visited[x] == False:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # dfs + visted\n",
    "    def validTree(self, n: int, edges: List[List[int]]) -> bool:\n",
    "        en = len(edges)\n",
    "        if en != n - 1:\n",
    "            return False\n",
    "        self.adjList = [[] for _ in range(n)]\n",
    "        \n",
    "        for i in range(len(edges)):\n",
    "            self.adjList[edges[i][0]].append(edges[i][1])\n",
    "            self.adjList[edges[i][1]].append(edges[i][0])\n",
    "        \n",
    "        self.visited = [False for _ in range(n)]\n",
    "        self.dfs(0)\n",
    "        \n",
    "        for i in range(n):\n",
    "            if self.visited[i] == False:\n",
    "                return False\n",
    "        return True\n",
    "    \n",
    "    def dfs(self,index) -> bool:\n",
    "        self.visited[index] = True\n",
    "        \n",
    "        for i in self.adjList[index]:\n",
    "            if self.visited[i] == False:\n",
    "                self.dfs(i)\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validTree(self, n: int, edges: List[List[int]]) -> bool:\n",
    "        if len(edges) != n - 1: return False\n",
    "        neighbors = [[] for _ in range(n)]\n",
    "        visited = [False] * n\n",
    "        for a, b in edges:\n",
    "            neighbors[a].append(b)\n",
    "            neighbors[b].append(a)\n",
    "        \n",
    "        def dfs(node):\n",
    "            visited[node] = True\n",
    "            for neighbor in neighbors[node]:\n",
    "                if not visited[neighbor]:\n",
    "                    dfs(neighbor)\n",
    "        \n",
    "        dfs(0)\n",
    "        return all(visited)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validTree(self, n: int, edges: List[List[int]]) -> bool:\n",
    "        adj = collections.defaultdict(set)\n",
    "        for a, b in edges:\n",
    "            adj[a].add(b)\n",
    "            adj[b].add(a)\n",
    "        deq = collections.deque([0])\n",
    "        visited = {0}\n",
    "        while deq:\n",
    "            i = deq.popleft()\n",
    "            # 由于需要修改adj[i]所以把adj[i]先拷贝一份再遍历\n",
    "            # 否则遍历一个在动态改变的数据结构容易出错\n",
    "            for j in list(adj[i]):\n",
    "                if j in visited:\n",
    "                    return False\n",
    "                deq.append(j)\n",
    "                visited.add(j)\n",
    "                # 一条边只能走一次, 使用边(i, j)后需要\n",
    "                # 把边(j, i)给删除掉\n",
    "                adj[j].remove(i)\n",
    "        return len(visited) == n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validTree(self, n: int, edges: List[List[int]]) -> bool:\n",
    "        en=len(edges)\n",
    "        if en!=n-1:\n",
    "            return False\n",
    "        ad=defaultdict(list)\n",
    "        for x,y in edges:\n",
    "            ad[x].append(y)\n",
    "            ad[y].append(x)\n",
    "        visited=[False for _ in range(n)]\n",
    "        def dfs(x):\n",
    "            visited[x]=True\n",
    "            for y in ad[x]:\n",
    "                if visited[y]==False:\n",
    "                    dfs(y)\n",
    "        dfs(0)\n",
    "        for x in range(n):\n",
    "            if visited[x]==False:\n",
    "                return False\n",
    "        return True\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validTree(self, n: int, edges: List[List[int]]) -> bool:\n",
    "        # TREE'S definition\n",
    "        if len(edges) != n - 1: \n",
    "            return False\n",
    "\n",
    "        # Construct Graph\n",
    "        graph = [[] for _ in range(n)]\n",
    "        for i, j in edges: \n",
    "            graph[i].append(j)\n",
    "            graph[j].append(i)\n",
    "        \n",
    "        visited = set()\n",
    "\n",
    "        def dfs(n, parent): \n",
    "            visited.add(n)\n",
    "\n",
    "            for neighbor in graph[n]: \n",
    "                if neighbor == parent: continue\n",
    "                if neighbor in visited or not dfs(neighbor, n): return False\n",
    "            \n",
    "            return True\n",
    "        \n",
    "\n",
    "        if not dfs(0, -1): \n",
    "            return False\n",
    "\n",
    "        return len(visited) == n\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validTree(self, n: int, edges: List[List[int]]) -> bool:\n",
    "        #解题思路：\n",
    "        #最小生成树，n个节点有n - 1条边，若不符合n-1条边，可以判否\n",
    "        #若等于n-1,则再进行判断\n",
    "        #dfs，使用标记法\n",
    "\n",
    "        if len(edges) != n - 1:\n",
    "            return False\n",
    "\n",
    "        def dfs(node,p):\n",
    "            for child in parent[node]:\n",
    "                if child == p:\n",
    "                    continue\n",
    "                if visited[child]:\n",
    "                    return False\n",
    "                visited[child] = 1\n",
    "                if dfs(child,node) == False:\n",
    "                    return False\n",
    "            return True\n",
    "        \n",
    "        parent = [[] for _ in range(n)]\n",
    "        visited = [0] * n\n",
    "        visited[0] = 1\n",
    "        for a,b in edges:\n",
    "            parent[a].append(b)\n",
    "            parent[b].append(a)\n",
    "        ans = dfs(0,-1)\n",
    "        if sum(visited) != n:\n",
    "            return False \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def validTree(self, n: int, edges: List[List[int]]) -> bool:\n",
    "        #一遍dfs即可，\n",
    "        #注意该题只有一棵树，如果有多颗树还不一样\n",
    "        if len(edges)!=n-1:return False #全联通，且无环，边数只能是n-1\n",
    "        graph=defaultdict(list)\n",
    "        for i,j in edges:\n",
    "            graph[i].append(j)\n",
    "            graph[j].append(i)\n",
    "        vis=set()\n",
    "        def dfs(i):\n",
    "            if i not in vis:\n",
    "                vis.add(i)\n",
    "                for j in graph[i]:\n",
    "                    dfs(j)\n",
    "        # for i in range(n):\n",
    "        #     if i not in vis:\n",
    "        #         dfs(i)\n",
    "        dfs(0)\n",
    "        return len(vis)==n\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validTree(self, n: int, edges: List[List[int]]) -> bool:\n",
    "        if len(edges) != n - 1:\n",
    "            return False\n",
    "        \n",
    "        adjList = [[] for _ in range(n)]\n",
    "        for k, v in edges:\n",
    "            adjList[k].append(v)\n",
    "            adjList[v].append(k)\n",
    "\n",
    "        seenSet = set()\n",
    "        \n",
    "        def dfs(nums):\n",
    "            if nums in seenSet:\n",
    "                return\n",
    "            seenSet.add(nums)\n",
    "            for num in adjList[nums]:\n",
    "                dfs(num)\n",
    "        dfs(0)\n",
    "        return len(seenSet) == n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validTree(self, n: int, edges: List[List[int]]) -> bool:\n",
    "        if len(edges) != n - 1:\n",
    "            return False\n",
    "        graph = {i:[] for i in range(n)}\n",
    "        for i, j in edges:\n",
    "            graph[i].append(j)\n",
    "            graph[j].append(i)\n",
    "        visited= set()\n",
    "        self.dfs(0, graph, visited)\n",
    "        return len(visited) == n\n",
    "\n",
    "    def dfs(self, index, graph, visited):\n",
    "        visited.add(index)\n",
    "        for j in graph[index]:\n",
    "            if j not in visited:\n",
    "                self.dfs(j, graph, visited)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validTree(self, n: int, edges: List[List[int]]) -> bool:\n",
    "        if len(edges) != n - 1: return False\n",
    "\n",
    "        dic = collections.defaultdict(list)\n",
    "        for a, b in edges:\n",
    "            dic[a].append(b)\n",
    "            dic[b].append(a)\n",
    "        \n",
    "        visited = set()\n",
    "\n",
    "        def dfs(node):\n",
    "            if node in visited: \n",
    "                return False\n",
    "            visited.add(node)\n",
    "\n",
    "            for n in dic[node]:\n",
    "                dfs(n)\n",
    "    \n",
    "        dfs(0)\n",
    "        for i in range(n):\n",
    "            if i not in visited: return False\n",
    "        return True \n",
    "        # for i in range(n):\n",
    "        #     if i not in visited:\n",
    "        #         if not dfs(i):\n",
    "        #             return False        \n",
    "        # return len(visited) == n - 1\n",
    "\n",
    "        # return True\n",
    "\n",
    "        # dic = collections.defaultdict(list)\n",
    "        # for a, b in edges:\n",
    "        #     dic[a].append(b)\n",
    "        #     dic[b].append(a)\n",
    "        \n",
    "        # visited = set()\n",
    "\n",
    "        # def dfs(node):\n",
    "        #     if node in visited:\n",
    "        #         return False\n",
    "        #     visited.add(node)\n",
    "\n",
    "        #     for neighbor in dic[node]:\n",
    "        #         if not dfs(neighbor):\n",
    "        #             return False\n",
    "\n",
    "        #     return True\n",
    "\n",
    "        # for i in range(n):\n",
    "        #     if i not in visited:\n",
    "        #         if not dfs(i):\n",
    "        #             return False\n",
    "\n",
    "        # # Ensure that there are no isolated nodes (trees with multiple components)\n",
    "        # return len(visited) == n - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Node:\n",
    "    def __init__(self):\n",
    "        self.isVisited = False\n",
    "        self.lj = []\n",
    "\n",
    "class Solution:\n",
    "    def validTree(self, n: int, edges: List[List[int]]) -> bool:\n",
    "        if len(edges) == 0 and n == 1:\n",
    "            return True\n",
    "        if len(edges) != (n - 1):\n",
    "            return False\n",
    "        if len(edges) == 0:\n",
    "            return False\n",
    "        if len(edges) == 1:\n",
    "            return True\n",
    "        \n",
    "        Nodes = []\n",
    "        for i in range(0, n):\n",
    "            newNode = Node()\n",
    "            Nodes.append(newNode)\n",
    "        for temp in edges:\n",
    "            node0 = temp[0]\n",
    "            node1 = temp[1]\n",
    "            Nodes[node0].lj.append(node1)\n",
    "            Nodes[node1].lj.append(node0)\n",
    "\n",
    "        def dsf(curNode):\n",
    "            #print(curNode.lj)\n",
    "            if curNode.isVisited == True:\n",
    "                return \n",
    "            if len(curNode.lj) == 0:\n",
    "                return \n",
    "            curNode.isVisited = True\n",
    "            for temp in curNode.lj:\n",
    "                dsf(Nodes[temp])\n",
    "\n",
    "        dsf(Nodes[0])\n",
    "        for temp in Nodes:\n",
    "            if temp.isVisited == False:\n",
    "                return False\n",
    "\n",
    "        return True\n",
    "\n",
    "            \n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validTree(self, n: int, edges: List[List[int]]) -> bool:\n",
    "        graph = [[] for _ in range(n)]\n",
    "        for u,v in edges:\n",
    "            graph[u].append(v)\n",
    "            graph[v].append(u)\n",
    "        w,g,b = 0,1,2\n",
    "        st = defaultdict(int)\n",
    "        def dfs(u,fa):\n",
    "            st[u] = g\n",
    "            for v in graph[u]:\n",
    "                if v == fa:\n",
    "                    continue\n",
    "                if st[v] == 0:\n",
    "                    dfs(v,u)\n",
    "                elif st[v] ==1:    \n",
    "                    return False\n",
    "            st[u] = b\n",
    "            return True\n",
    "        if not dfs(0,-1):\n",
    "            return False\n",
    "        for i in range(n):\n",
    "            if st[i]!=b:\n",
    "                return False\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validTree(self, n: int, edges: List[List[int]]) -> bool:\n",
    "        if not n:\n",
    "            return True\n",
    "        if len(edges) != n - 1:\n",
    "            return False\n",
    "        adj = defaultdict(list)\n",
    "        for i, j in edges:\n",
    "            adj[i].append(j)\n",
    "            adj[j].append(i)\n",
    "        visit = set()\n",
    "        def dfs(i, pre):\n",
    "            if i in visit:\n",
    "                return False\n",
    "            visit.add(i)\n",
    "            for j in adj[i]:\n",
    "                if j == pre:\n",
    "                    continue\n",
    "                if not dfs(j, i):\n",
    "                    return False\n",
    "            return True\n",
    "        return dfs(0, -1) and n == len(visit)\n",
    "\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validTree(self, n: int, edges: List[List[int]]) -> bool:\n",
    "        if len(edges)!=n-1:\n",
    "            return False\n",
    "        visited = [False]*n\n",
    "        ans = collections.defaultdict(list)\n",
    "        count = 0\n",
    "        for k,v in edges:\n",
    "            ans[k].append(v)\n",
    "            ans[v].append(k)\n",
    "        print(ans)\n",
    "        def dfs(u):\n",
    "            visited[u]=True\n",
    "            for i in ans[u]:\n",
    "                if visited[i]==False:\n",
    "                    dfs(i)\n",
    "            #return\n",
    "        print(visited)\n",
    "        for i in range(n):\n",
    "            if visited[i]==False:\n",
    "                count+=1\n",
    "                dfs(i)\n",
    "        if count>1:\n",
    "            return False\n",
    "        return True\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validTree(self, n: int, edges: List[List[int]]) -> bool:\n",
    "        g = defaultdict(list)\n",
    "        for u,v in edges:\n",
    "            g[u].append(v)\n",
    "            g[v].append(u)\n",
    "        #print(g)\n",
    "        st = defaultdict(int)\n",
    "        \n",
    "        def dfs(u,f):\n",
    "            st[u] = 1\n",
    "            for v in g[u]:\n",
    "                if v==f:\n",
    "                    continue\n",
    "                if st[v] ==0:\n",
    "                    dfs(v,u)\n",
    "                elif st[v] == 1:\n",
    "                    return False\n",
    "                else:\n",
    "                    continue\n",
    "            st[u] = 2\n",
    "            return True\n",
    "\n",
    "\n",
    "        if not dfs(0,-1):\n",
    "            return False\n",
    "        for i in range(n):\n",
    "            if st[i] ==0:\n",
    "                return False\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validTree(self, n: int, edges: List[List[int]]) -> bool:\n",
    "        # 合法的树结构，就是不存在环路\n",
    "        # 因此先建图，然后判断是否有环路即可,拓扑排序判断,度为1的结点\n",
    "        g = defaultdict(list)\n",
    "        # 首先判断整个图是否是连通的\n",
    "        deg = [0]*n\n",
    "        for u,v in edges:\n",
    "            g[u].append(v)\n",
    "            g[v].append(u)\n",
    "            deg[u] += 1\n",
    "            deg[v] += 1\n",
    "        vis = set()\n",
    "        def dfs(node):\n",
    "            for nxt in g[node]:\n",
    "                if nxt not in vis:\n",
    "                    vis.add(nxt)\n",
    "                    dfs(nxt)\n",
    "        vis.add(0)\n",
    "        dfs(0)\n",
    "        if len(vis)!=n:\n",
    "            return False\n",
    "\n",
    "\n",
    "\n",
    "        queue = deque([i for i,num in enumerate(deg) if num == 1])\n",
    "        vis = set([i for i,num in enumerate(deg) if num == 1])\n",
    "        while queue:\n",
    "            node = queue.popleft()\n",
    "            for nxt in g[node]:\n",
    "                if nxt not in vis:\n",
    "                    deg[nxt] -= 1\n",
    "                    if deg[nxt] == 1:\n",
    "                        queue.append(nxt) \n",
    "                        vis.add(nxt)\n",
    "        \n",
    "        for i in deg:\n",
    "            if i > 1:\n",
    "                return False\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validTree(self, n: int, edges: List[List[int]]) -> bool:\n",
    "        #DFS\n",
    "        graph = defaultdict(list)\n",
    "        for x, y in edges:\n",
    "            graph[x].append(y)\n",
    "            graph[y].append(x)\n",
    "        lenEdges = len(edges)\n",
    "        visited = set()\n",
    "\n",
    "        def dfs(node):\n",
    "            nonlocal lenEdges\n",
    "            visited.add(node)\n",
    "            for neighbour in graph[node]:\n",
    "                if neighbour not in visited:\n",
    "                    visited.add(neighbour)\n",
    "                    lenEdges -= 1\n",
    "                    dfs(neighbour)\n",
    "        dfs(0)\n",
    "        print(visited, lenEdges)\n",
    "        return len(visited) == n and lenEdges == 0\n",
    "\n",
    "        #n个节点，只要有n-1条边，且连通，就是无环图。len(visited) == n ensure every node in a single group\n",
    "\n",
    "\n",
    "\n",
    "       \n",
    "\n",
    "       \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UF:\n",
    "    def __init__(self, n):\n",
    "        self.count = n\n",
    "        self.parent = [i for i in range(n)]\n",
    "\n",
    "    def find(self, i):\n",
    "        if self.parent[i] != i:\n",
    "            self.parent[i] = self.find(self.parent[i])\n",
    "        return self.parent[i]\n",
    "\n",
    "    def union(self, p, q):\n",
    "        if self.find(p) == self.find(q):\n",
    "            return\n",
    "        self.parent[self.find(p)] = q\n",
    "        self.count -= 1\n",
    "\n",
    "class Solution:\n",
    "    def validTree(self, n: int, edges: List[List[int]]) -> bool:\n",
    "        uf = UF(n)\n",
    "        for from_, to_ in edges:\n",
    "            if uf.find(from_) == uf.find(to_) :\n",
    "                return False\n",
    "            uf.union(from_, to_)\n",
    "        return True if uf.count == 1 else False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validTree(self, n: int, edges: List[List[int]]) -> bool:\n",
    "        if len(edges) != n - 1:\n",
    "            return False\n",
    "        adj = collections.defaultdict(set)\n",
    "        for a, b in edges:\n",
    "            adj[a].add(b)\n",
    "            adj[b].add(a)\n",
    "        visited = set()\n",
    "\n",
    "        def dfs(i):\n",
    "            visited.add(i)\n",
    "            for j in adj[i]:\n",
    "                if j not in visited:\n",
    "                    dfs(j)\n",
    "            return\n",
    "        \n",
    "        dfs(0)\n",
    "        return len(visited) == n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UFS:\n",
    "    def __init__(self, n):\n",
    "        self.par = [i for i in range(n)]\n",
    "        self.rank = [0 for _ in range(n)]\n",
    "        self.cc = n\n",
    "    \n",
    "    def find(self, p):\n",
    "        if p == self.par[p]:\n",
    "            return p \n",
    "        p = self.par[p]\n",
    "        return self.find(p)\n",
    "    \n",
    "    def union(self, n1, n2):\n",
    "        p1, p2 = self.find(n1),self.find(n2)\n",
    "        if p1 == p2:\n",
    "            return False\n",
    "        self.par[p1] = p2\n",
    "        self.cc -= 1\n",
    "        return True\n",
    "        \n",
    "class Solution:\n",
    "    def validTree(self, n: int, edges: List[List[int]]) -> bool:\n",
    "        ufs = UFS(n)\n",
    "        for u,v in edges:\n",
    "            if not ufs.union(u, v):\n",
    "                return False\n",
    "        return ufs.cc == 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validTree(self, n: int, edges: List[List[int]]) -> bool:\n",
    "        def find(x):\n",
    "            if p[x] != x:\n",
    "                p[x] = find(p[x])\n",
    "            return p[x]\n",
    "\n",
    "        p = list(range(n))\n",
    "        for a, b in edges:\n",
    "            if find(a) == find(b):\n",
    "                return False\n",
    "            p[find(a)] = find(b)\n",
    "            n -= 1\n",
    "        return n == 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validTree(self, n: int, edges: List[List[int]]) -> bool:\n",
    "        class UF:\n",
    "            def __init__(self, n):\n",
    "                self.cnt = n\n",
    "                self.parent = [i for i in range(n)]\n",
    "            \n",
    "            def find(self, x):\n",
    "                if self.parent[x] != x:\n",
    "                    self.parent[x] = self.find(self.parent[x])\n",
    "                return self.parent[x]\n",
    "            \n",
    "            def union(self, p, q):\n",
    "                root_p = self.find(p)\n",
    "                root_q = self.find(q)\n",
    "                if root_p == root_q:\n",
    "                    return \n",
    "                self.parent[root_p] = root_q\n",
    "                self.cnt -= 1\n",
    "            \n",
    "            def connected(self, p, q):\n",
    "                root_p = self.find(p)\n",
    "                root_q = self.find(q)\n",
    "                if root_p == root_q:\n",
    "                    return True\n",
    "                else:\n",
    "                    return False\n",
    "        \n",
    "        uf = UF(n)\n",
    "        for p, q in edges:\n",
    "            if uf.connected(p, q):\n",
    "                return False\n",
    "            uf.union(p, q)  \n",
    "        return uf.cnt == 1          "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validTree(self, n: int, edges: List[List[int]]) -> bool:\n",
    "        p = [i for i in range(n)]\n",
    "        \n",
    "        def find(x):\n",
    "            if p[x] != x:\n",
    "                p[x] = find(p[x])\n",
    "            return p[x]\n",
    "\n",
    "        def merge(a, b):\n",
    "            p[find(a)] = find(b)\n",
    "\n",
    "        \n",
    "        for x, y in edges:\n",
    "            if find(x) == find(y):\n",
    "                return False\n",
    "            merge(x, y)\n",
    "            \n",
    "        cnt = 0\n",
    "        for i in range(n):\n",
    "            cnt += p[i] == i\n",
    "        \n",
    "        if cnt == 1:\n",
    "            return True\n",
    "        else:\n",
    "            return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self,n):\n",
    "        self.n = n\n",
    "        self.part = n\n",
    "        self.fa = list(range(n))\n",
    "    def find(self,x):\n",
    "        if x != self.fa[x]:\n",
    "            self.fa[x] = self.find(self.fa[x])\n",
    "        return self.fa[x]\n",
    "    def union(self,x,y):\n",
    "        rx = self.find(x)\n",
    "        ry = self.find(y)\n",
    "        if rx == ry:\n",
    "            return False\n",
    "        \n",
    "        self.fa[rx] = ry\n",
    "        self.part -= 1\n",
    "        return True\n",
    "    def in_same_part(self,x,y):\n",
    "        return self.find(x)==self.find(y)\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def validTree(self, n: int, edges: List[List[int]]) -> bool:\n",
    "        uf = UnionFind(n)\n",
    "        for x,y in edges:\n",
    "            if not uf.union(x,y):\n",
    "                return False\n",
    "        return uf.part ==1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validTree(self, n: int, edges: List[List[int]]) -> bool:\n",
    "        p = [i for i in range(n)]\n",
    "        \n",
    "        def find(x):\n",
    "            if p[x] != x:\n",
    "                p[x] = find(p[x])\n",
    "            return p[x]\n",
    "\n",
    "        def merge(a, b):\n",
    "            p[find(a)] = find(b)\n",
    "\n",
    "        # 没有环\n",
    "        for x, y in edges:\n",
    "            if find(x) == find(y):\n",
    "                return False\n",
    "            merge(x, y)\n",
    "\n",
    "        cnt = 0\n",
    "        for i in range(n):\n",
    "            cnt += p[i] == i\n",
    "        \n",
    "        # 连通图\n",
    "        if cnt == 1:\n",
    "            return True\n",
    "        else:\n",
    "            return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class union_find:\n",
    "    def __init__(self, n):\n",
    "        self.parent = [i for i in range(n)]\n",
    "        self.count = n\n",
    "    def union(self, x, y):\n",
    "        parent_x = self.find(x)\n",
    "        parent_y = self.find(y)\n",
    "        if parent_x == parent_y:\n",
    "            return\n",
    "        self.parent[parent_x] = parent_y\n",
    "        self.count -= 1\n",
    "    def find(self, x):\n",
    "        if x!=self.parent[x]:\n",
    "            self.parent[x] = self.find(self.parent[x])\n",
    "        return self.parent[x]\n",
    "    def connected(self, x, y):\n",
    "        parent_x = self.find(x)\n",
    "        parent_y = self.find(y)\n",
    "        return parent_x == parent_y\n",
    "\n",
    "class Solution:\n",
    "    def validTree(self, n: int, edges: List[List[int]]) -> bool:\n",
    "        uf = union_find(n)\n",
    "        for i, j in edges:\n",
    "            if uf.connected(i, j):\n",
    "                return False\n",
    "            uf.union(i, j)\n",
    "        \n",
    "        return uf.count==1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validTree(self, n: int, edges: List[List[int]]) -> bool:\n",
    "        num_edge = len(edges)\n",
    "        if num_edge != n-1:\n",
    "            return False\n",
    "        if not edges:\n",
    "            return True\n",
    "            \n",
    "        graph = {}\n",
    "        for edge in edges:\n",
    "            graph[edge[0]] = graph.get(edge[0],[]) + [edge[1]]\n",
    "            graph[edge[1]] = graph.get(edge[1],[]) + [edge[0]]\n",
    "        \n",
    "        \n",
    "        visited = []\n",
    "        def dfs(node):\n",
    "            if node in visited:\n",
    "                return False\n",
    "            visited.append(node)\n",
    "            \n",
    "            for i in graph[node]:\n",
    "                graph[i].remove(node)\n",
    "                if not dfs(i):\n",
    "                    return False\n",
    "            return True\n",
    "\n",
    "\n",
    "        return dfs(edges[0][0])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validTree(self, n: int, edges: List[List[int]]) -> bool:\n",
    "        p = [i for i in range(n)]\n",
    "        \n",
    "        def find(x):\n",
    "            if p[x] != x:\n",
    "                p[x] = find(p[x])\n",
    "            return p[x]\n",
    "\n",
    "        def merge(a, b):\n",
    "            p[find(a)] = find(b)\n",
    "\n",
    "        \n",
    "        for x, y in edges:\n",
    "            if find(x) == find(y):\n",
    "                return False\n",
    "            merge(x, y)\n",
    "            \n",
    "        cnt = 0\n",
    "        for i in range(n):\n",
    "            cnt += p[i] == i\n",
    "        \n",
    "        if cnt == 1:\n",
    "            return True\n",
    "        else:\n",
    "            return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validTree(self, n: int, edges: List[List[int]]) -> bool:\n",
    "        p = [i for i in range(n)]\n",
    "        \n",
    "        def find(x):\n",
    "            if p[x] != x:\n",
    "                p[x] = find(p[x])\n",
    "            return p[x]\n",
    "\n",
    "        def merge(a, b):\n",
    "            p[find(a)] = find(b)\n",
    "\n",
    "        \n",
    "        for x, y in edges:\n",
    "            if find(x) == find(y):\n",
    "                return False\n",
    "            merge(x, y)\n",
    "            \n",
    "        cnt = 0\n",
    "        for i in range(n):\n",
    "            cnt += p[i] == i\n",
    "        \n",
    "        if cnt == 1:\n",
    "            return True\n",
    "        else:\n",
    "            return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validTree(self, n: int, edges: List[List[int]]) -> bool:\n",
    "        def build(n):\n",
    "            parent = [0] * n\n",
    "            for i in range(n):\n",
    "                parent[i] = i\n",
    "            return parent\n",
    "        \n",
    "        def find(x):\n",
    "            if parent[x] != x:\n",
    "                parent[x] = find(parent[x])\n",
    "            return parent[x]\n",
    "        \n",
    "        def union(p, q):\n",
    "            nonlocal count\n",
    "            P = find(p)\n",
    "            Q = find(q)\n",
    "            if P == Q:\n",
    "                return \n",
    "            else:\n",
    "                parent[P] = Q\n",
    "                count -= 1\n",
    "        \n",
    "        def connect(p, q):\n",
    "            P = find(p)\n",
    "            Q = find(q)\n",
    "            return P == Q\n",
    "        \n",
    "        count = n\n",
    "        parent = build(n)\n",
    "        for edge in edges:\n",
    "            if connect(edge[0], edge[1]):\n",
    "                return False\n",
    "            union(edge[0], edge[1])\n",
    "        return count == 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validTree(self, n: int, edges: List[List[int]]) -> bool:\n",
    "        parent = [i for i in range(n)]\n",
    "        clusters = n\n",
    "\n",
    "        def find(p):\n",
    "            if parent[p] != p:\n",
    "                parent[p] = find(parent[p])\n",
    "            return parent[p]\n",
    "\n",
    "        def union(p,q):\n",
    "            if find(p) == find(q):\n",
    "                return True \n",
    "            else:\n",
    "                parent[find(p)] = find(q)\n",
    "                return False  \n",
    "\n",
    "        for i, j in edges:\n",
    "            if union(i,j):\n",
    "                return False\n",
    "            else:\n",
    "                clusters -=1 \n",
    "        return True if clusters==1 else False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import *\n",
    "from sortedcontainers import *\n",
    "from heapq import *\n",
    "from sys import *\n",
    "from math import *\n",
    "from itertools import *\n",
    "from functools import *\n",
    "from string import *\n",
    "from bisect import *\n",
    "\n",
    "class IdentityDefaultDict(defaultdict):\n",
    "    '''\n",
    "    该类用于处理并查集初始化的恒等映射\n",
    "    '''\n",
    "    def __missing__(self, key):\n",
    "        return key\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, n=None):\n",
    "        self.parent = IdentityDefaultDict()\n",
    "        if n: self.parent = list(range(n))\n",
    "    def find(self, x):\n",
    "        if self.parent[x] != x: self.parent[x] = self.find(self.parent[x])\n",
    "        return self.parent[x]\n",
    "    def merge(self, x, y):\n",
    "        x, y = self.find(x), self.find(y)\n",
    "        if x != y: self.parent[x] = y\n",
    "    def get_group_count(self):\n",
    "        return len(set(self.find(x) for x in self.parent))\n",
    "\n",
    "class Solution:\n",
    "    def validTree(self, n: int, edges: List[List[int]]) -> bool:\n",
    "        uf = UnionFind(n)\n",
    "        for x, y in edges:\n",
    "            uf.merge(x, y)\n",
    "        return len(set(map(uf.find, list(range(n))))) == 1 and len(edges) + 1 == n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UF:\n",
    "    def __init__(self, n):\n",
    "        self.parent = [i for i in range(n)]\n",
    "        self.count = n\n",
    "\n",
    "    def union(self,x,y):\n",
    "        parentX = self.find(x)\n",
    "        parentY = self.find(y)\n",
    "        if not parentX == parentY:\n",
    "            self.count -= 1\n",
    "            self.parent[parentX] = parentY\n",
    "        return\n",
    "\n",
    "    def find(self,x):\n",
    "        if self.parent[x] != x:\n",
    "            x = self.find(self.parent[x])\n",
    "        return x\n",
    "\n",
    "class Solution:\n",
    "    def validTree(self, n: int, edges: List[List[int]]) -> bool:\n",
    "\n",
    "        if n == 1:\n",
    "            return True\n",
    "\n",
    "        # n = len(edges)\n",
    "        degree = {i : 0 for i in range(n)}\n",
    "        graph = {i : list() for i in range(n)}\n",
    "        \n",
    "        for edge in edges:\n",
    "            degree[edge[1]] += 1\n",
    "            degree[edge[0]] += 1\n",
    "            graph[edge[0]].append(edge[1])   \n",
    "            graph[edge[1]].append(edge[0])\n",
    "\n",
    "        # print(graph)\n",
    "        queue = list()\n",
    "        for key in degree.keys():\n",
    "            if degree[key] == 1:\n",
    "                queue.append(key)\n",
    "        count = 0\n",
    "\n",
    "        while queue:\n",
    "            count +=1 \n",
    "            cur = queue.pop()\n",
    "            # print(cur)\n",
    "            for node in graph[cur]:\n",
    "                # print(node)\n",
    "                degree[node] -= 1\n",
    "                if degree[node] == 1:\n",
    "                    queue.append(node)\n",
    "        # print(count)\n",
    "        # print(degree)\n",
    "        myUF = UF(n)\n",
    "        for edge in edges:\n",
    "            myUF.union(edge[0],edge[1])\n",
    "        # print(myUF.count)\n",
    "        if myUF.count != 1:\n",
    "            return False\n",
    "        else:\n",
    "            return count == n\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validTree(self, n: int, edges: List[List[int]]) -> bool:\n",
    "        \n",
    "        f = {}\n",
    "        \n",
    "        def find(x):\n",
    "            f.setdefault(x, x)\n",
    "            if x != f[x]:\n",
    "                f[x] = find(f[x])\n",
    "            return f[x]\n",
    "        \n",
    "        def union(x, y):\n",
    "            f[find(x)] = find(y)\n",
    "            \n",
    "        for x, y in edges:\n",
    "            tmp1 = find(x)\n",
    "            tmp2 = find(y)\n",
    "            if tmp1 == tmp2:\n",
    "                return False\n",
    "            union(x, y)\n",
    "        return len(set(find(x) for x in range(n))) == 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validTree(self, n: int, edges: List[List[int]]) -> bool:\n",
    "        visited = [False] * n\n",
    "        successors = [[] for _ in range(n)]\n",
    "\n",
    "        for u, v in edges:\n",
    "            successors[u].append(v)\n",
    "            successors[v].append(u)\n",
    "        \n",
    "        def dfs(prev, current):\n",
    "            if visited[current]:\n",
    "                return False\n",
    "            \n",
    "            visited[current] = True\n",
    "\n",
    "            for v in successors[current]:\n",
    "                if prev == v:\n",
    "                    continue\n",
    "                \n",
    "                if not dfs(current, v):\n",
    "                    return False\n",
    "            \n",
    "            return True\n",
    "        \n",
    "        return dfs(-1, 0) and all(visited)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validTree(self, n: int, edges: List[List[int]]) -> bool:\n",
    "        # 创建邻接表\n",
    "        graph = [[] for _ in range(n)]\n",
    "        for a, b in edges:\n",
    "            graph[a].append(b)\n",
    "            graph[b].append(a)\n",
    "        \n",
    "        # 标记节点是否访问过\n",
    "        visited = [False] * n\n",
    "\n",
    "        # dfs判断是否有环\n",
    "        def dfs(node, parent):\n",
    "            visited[node] = True\n",
    "            for neighbor in graph[node]:\n",
    "                if not visited[neighbor]:\n",
    "                    if dfs(neighbor, node):\n",
    "                        return True\n",
    "                elif neighbor != parent:\n",
    "                    return True\n",
    "            return False\n",
    "        if dfs(0, -1):\n",
    "            return False\n",
    "        return all(visited)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validTree(self, n: int, edges: List[List[int]]) -> bool:\n",
    "        g = [[] for _ in range(n)]\n",
    "\n",
    "        indegree = [0] * n\n",
    "        for a, b in edges:\n",
    "            g[a].append(b)\n",
    "            g[b].append(a)\n",
    "            indegree[a] += 1\n",
    "            indegree[b] += 1\n",
    "        \n",
    "        visited = [False] * n\n",
    "        def visit(node: int) -> None:\n",
    "            if visited[node]: return\n",
    "            visited[node] = True\n",
    "            for nextNode in g[node]:\n",
    "                visit(nextNode)\n",
    "        visit(0)\n",
    "        if any(not x for x in visited):\n",
    "            return False\n",
    "\n",
    "        q = deque()\n",
    "        for i in range(n):\n",
    "            if indegree[i] == 1:\n",
    "                q.append(i)\n",
    "        \n",
    "        while q:\n",
    "            cur = q.popleft()\n",
    "            for nextNode in g[cur]:\n",
    "                indegree[nextNode] -= 1\n",
    "                if indegree[nextNode] == 1:\n",
    "                    q.append(nextNode)\n",
    "        \n",
    "        return all(x == 0 for x in indegree)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validTree(self, n: int, edges: List[List[int]]) -> bool:\n",
    "        if not n:\n",
    "            return True\n",
    "\n",
    "        visited = set()\n",
    "        graph = {i : [] for i in range(n) }\n",
    "\n",
    "        for n1, n2 in edges:\n",
    "            graph[n1].append(n2)\n",
    "            graph[n2].append(n1)\n",
    "\n",
    "\n",
    "        @cache\n",
    "        def helper(i, prev):\n",
    "            if i in visited:\n",
    "                return False\n",
    "            \n",
    "            visited.add(i)\n",
    "\n",
    "            for j in graph[i]:\n",
    "                if j == prev:\n",
    "                    continue\n",
    "                if not helper(j, i):\n",
    "                    return False\n",
    "                visited.add(j)\n",
    "            return True\n",
    "        \n",
    "        return helper(0, -1) and len(visited) == n\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validTree(self, n: int, edges: List[List[int]]) -> bool:\n",
    "        graph={}\n",
    "        len_edges=len(edges)\n",
    "        for x,y in edges:\n",
    "            if x not in graph:\n",
    "                graph[x]=[]\n",
    "            graph[x].append(y)\n",
    "            if y not in graph:\n",
    "                graph[y]=[]\n",
    "            graph[y].append(x)\n",
    "        \n",
    "        vistied=set()\n",
    "        def dfs(i):\n",
    "            nonlocal len_edges\n",
    "            vistied.add(i)\n",
    "            for j in graph.get(i,[]):\n",
    "                if j not in vistied:\n",
    "                    len_edges-=1\n",
    "                    dfs(j)\n",
    "        dfs(0)\n",
    "\n",
    "        return len(vistied)==n and len_edges==0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validTree(self, n: int, edges: List[List[int]]) -> bool:\n",
    "        from collections import defaultdict\n",
    "\n",
    "        parent_dict = {}\n",
    "        for i in range(n):\n",
    "            parent_dict[i] = i\n",
    "        \n",
    "        def find(i):\n",
    "            if parent_dict[i] != i:\n",
    "                return find(parent_dict[i])\n",
    "            else:\n",
    "                return i\n",
    "        \n",
    "        def merge(i, j):\n",
    "            if find(i) != find(j):\n",
    "                parent_dict[find(i)] = find(j)\n",
    "        \n",
    "        for i, j in edges:\n",
    "            merge(i, j)\n",
    "        \n",
    "        parent_set = set()\n",
    "        for i in range(n):\n",
    "            parent_set.add(find(i))\n",
    "        if len(parent_set) != 1:\n",
    "            return False\n",
    "\n",
    "\n",
    "        visited = [0] * n\n",
    "\n",
    "\n",
    "        edge_dict = defaultdict(list)\n",
    "        for i, j in edges:\n",
    "            edge_dict[i].append(j)\n",
    "            edge_dict[j].append(i)\n",
    "\n",
    "        res = True\n",
    "        \n",
    "        def dfs(i, reject=None):\n",
    "            nonlocal res\n",
    "            if not res:\n",
    "                return\n",
    "            if visited[i] == 2:\n",
    "                return\n",
    "            visited[i] = 1\n",
    "            for j in edge_dict[i]:\n",
    "                if j == reject:\n",
    "                    continue\n",
    "                if visited[j] == 1:\n",
    "                    res = False\n",
    "                    return 0\n",
    "                dfs(j, i)\n",
    "            visited[i] = 2\n",
    "            \n",
    "        \n",
    "        for i in range(n):\n",
    "            dfs(i)\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validTree(self, n: int, edges: List[List[int]]) -> bool:\n",
    "        color = [0] * n\n",
    "        adj = collections.defaultdict(list)\n",
    "        for a, b in edges:\n",
    "            adj[a].append(b)\n",
    "            adj[b].append(a)\n",
    "\n",
    "        def dfs(i, prev):\n",
    "            if color[i] == 2:\n",
    "                return True\n",
    "            if color[i] == 1:\n",
    "                return False\n",
    "            color[i] = 1\n",
    "            for j in adj[i]:\n",
    "                # 必须加个prev, 否则这次从节点0到2, 然后下一次从2走到0\n",
    "                # 会因为color[0]等于1误判为有环\n",
    "                if prev == j:\n",
    "                    continue\n",
    "                if not dfs(j, i):\n",
    "                    return False\n",
    "            color[i] = 2\n",
    "            return True\n",
    "        \n",
    "        # 图无环且外层DFS可以遍历全部节点\n",
    "        dfs(0, -1)\n",
    "        return all(color[i] == 2 for i in range(n))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validTree(self, n: int, edges: List[List[int]]) -> bool:\n",
    "        dic={i:set() for i in range(n)}\n",
    "        #temp=set()\n",
    "        for i in edges:\n",
    "            dic[i[0]].add(i[1])\n",
    "            dic[i[1]].add(i[0])\n",
    "        print(dic)\n",
    "        ok=[True for i in range(n)]\n",
    "        visited=[False for i in range(n)]\n",
    "        def dfs(x,cur):\n",
    "            visited[cur]=True\n",
    "            test=dic[cur]\n",
    "           \n",
    "            \n",
    "            \n",
    "            for i in test:\n",
    "                if i in x and i!=x[-2]:\n",
    "                    ok[i]=False\n",
    "                    return False\n",
    "                \n",
    "                if i in x and i==x[-2]:\n",
    "                   \n",
    "                    continue\n",
    "                if visited[i]:\n",
    "                    continue\n",
    "                x.append(i)\n",
    "                dfs(x,i)\n",
    "               \n",
    "                \n",
    "                x.pop()\n",
    "            return True\n",
    "        if not dfs([0],0):\n",
    "            return False\n",
    "        for i in range(n):\n",
    "            if not ok[i] or not visited[i]:\n",
    "                return False\n",
    "        \n",
    "        \n",
    "        return True       \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validTree(self, n: int, edges: List[List[int]]) -> bool:\n",
    "        # 树结构：1.无环；2.以0开始可遍历所有node\n",
    "\n",
    "        graph = [[] for i in range(n)]\n",
    "        for x,y in edges:\n",
    "            graph[x].append(y)\n",
    "            graph[y].append(x)\n",
    "\n",
    "        def dfs(cur,parent):\n",
    "            visited[cur] = True\n",
    "            for i in graph[cur]:\n",
    "                if not visited[i]:\n",
    "                    if dfs(i,cur):\n",
    "                        return True\n",
    "                elif parent != i:\n",
    "                    return True\n",
    "            return False\n",
    "\n",
    "        visited = [False for _ in range(n)]\n",
    "        if dfs(0,-1):\n",
    "            return False\n",
    "        return all(visited)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def validTree(self, n: int, edges: List[List[int]]) -> bool:\n",
    "        \n",
    "        def dfs(cur_node, last_node): # 环检测，有环返回false\n",
    "            visited[cur_node] = True\n",
    "            # 考虑三种情况：1. 没访问 2. 访问但不成环 3. 有环但是环上只有两个节点（only visited[next_node] == True 但next_node == last_node）\n",
    "            for next_node in graph[cur_node]:\n",
    "                if visited[next_node] and next_node != last_node:\n",
    "                    return False\n",
    "                if not visited[next_node]:\n",
    "                    if not dfs(next_node, cur_node):\n",
    "                        return False\n",
    "            return True\n",
    "            \n",
    "        \n",
    "        #### 建图\n",
    "        # graph = defaultdict(lambda: -1)\n",
    "        # graph = defaultdict(int) # 默认为0\n",
    "        graph = defaultdict(list)\n",
    "        for end1, end2 in edges:\n",
    "            if end1 not in graph:\n",
    "                graph[end1] = [end2]\n",
    "            else:\n",
    "                graph[end1].append(end2)\n",
    "            if end2 not in graph:\n",
    "                graph[end2] = [end1]\n",
    "            else:\n",
    "                graph[end2].append(end1)\n",
    "        # print(graph)\n",
    "        \n",
    "        #### DFS\n",
    "        visited = [False] * n\n",
    "        no_circle_detect_res = dfs(0, -1)\n",
    "        # print(visited)\n",
    "        sum_visited = sum(visited)\n",
    "        # print(sum_visited)\n",
    "        if no_circle_detect_res and sum_visited == n:\n",
    "            return True\n",
    "        else:\n",
    "            return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def validTree(self, n: int, edges: List[List[int]]) -> bool:\n",
    "        \n",
    "        def dfs(cur_node, last_node): # 环检测，有环返回false\n",
    "            visited[cur_node] = True\n",
    "            # 考虑三种情况：1. 没访问 2. 访问但不成环 3. 有环但是环上只有两个节点（only visited[next_node] == True 但next_node == last_node）\n",
    "            for next_node in graph[cur_node]:\n",
    "                if visited[next_node] and next_node != last_node:\n",
    "                    return False\n",
    "                if not visited[next_node]:\n",
    "                    if not dfs(next_node, cur_node):\n",
    "                        return False\n",
    "            return True\n",
    "            \n",
    "        \n",
    "        #### 建图\n",
    "        # graph = defaultdict(lambda: -1)\n",
    "        # graph = defaultdict(int) # 默认为0\n",
    "        graph = defaultdict(list)\n",
    "        for end1, end2 in edges:\n",
    "            if end1 not in graph:\n",
    "                graph[end1] = [end2]\n",
    "            else:\n",
    "                graph[end1].append(end2)\n",
    "            if end2 not in graph:\n",
    "                graph[end2] = [end1]\n",
    "            else:\n",
    "                graph[end2].append(end1)\n",
    "        # print(graph)\n",
    "        \n",
    "        #### DFS\n",
    "        visited = [False] * n\n",
    "        no_circle_detect_res = dfs(0, -1)\n",
    "        # print(visited)\n",
    "        sum_visited = sum(visited)\n",
    "        # print(sum_visited)\n",
    "        if no_circle_detect_res and sum_visited == n:\n",
    "            return True\n",
    "        else:\n",
    "            return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validTree(self, n: int, edges: List[List[int]]) -> bool:\n",
    "        if not n:\n",
    "            return True\n",
    "        adj = defaultdict(list)\n",
    "        for i, j in edges:\n",
    "            adj[i].append(j)\n",
    "            adj[j].append(i)\n",
    "        visit = set()\n",
    "        def dfs(i, pre):\n",
    "            if i in visit:\n",
    "                return False\n",
    "            visit.add(i)\n",
    "            for j in adj[i]:\n",
    "                if j == pre:\n",
    "                    continue\n",
    "                if not dfs(j, i):\n",
    "                    return False\n",
    "            return True\n",
    "        return dfs(0, -1) and n == len(visit)\n",
    "\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def validTree(self, n: int, edges: List[List[int]]) -> bool:\n",
    "        \n",
    "        def dfs(cur_node, last_node): # 环检测，有环返回false\n",
    "            visited[cur_node] = True\n",
    "            # 考虑三种情况：1. 没访问 2. 访问但不成环 3. 有环但是环上只有两个节点（only visited[next_node] == True 但next_node == last_node）\n",
    "            for next_node in graph[cur_node]:\n",
    "                if visited[next_node] and next_node != last_node:\n",
    "                    return False\n",
    "                if not visited[next_node]:\n",
    "                    if not dfs(next_node, cur_node):\n",
    "                        return False\n",
    "            return True\n",
    "            \n",
    "        \n",
    "        #### 建图\n",
    "        # graph = defaultdict(lambda: -1)\n",
    "        # graph = defaultdict(int) # 默认为0\n",
    "        graph = defaultdict(list)\n",
    "        for end1, end2 in edges:\n",
    "            if end1 not in graph:\n",
    "                graph[end1] = [end2]\n",
    "            else:\n",
    "                graph[end1].append(end2)\n",
    "            if end2 not in graph:\n",
    "                graph[end2] = [end1]\n",
    "            else:\n",
    "                graph[end2].append(end1)\n",
    "        # print(graph)\n",
    "        \n",
    "        #### DFS\n",
    "        visited = [False] * n\n",
    "        no_circle_detect_res = dfs(0, -1)\n",
    "        # print(visited)\n",
    "        sum_visited = sum(visited)\n",
    "        # print(sum_visited)\n",
    "        if no_circle_detect_res and sum_visited == n:\n",
    "            return True\n",
    "        else:\n",
    "            return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validTree(self, n: int, edges: List[List[int]]) -> bool:\n",
    "        # graph={}\n",
    "        # len_edges=len(edges)\n",
    "        # for x,y in edges:\n",
    "        #     if x not in graph:\n",
    "        #         graph[x]=[]\n",
    "        #     graph[x].append(y)\n",
    "        #     if y not in graph:\n",
    "        #         graph[y]=[]\n",
    "        #     graph[y].append(x)\n",
    "        \n",
    "        # vistied=set()\n",
    "        # def dfs(i):\n",
    "        #     nonlocal len_edges\n",
    "        #     vistied.add(i)\n",
    "        #     for j in graph.get(i,[]):\n",
    "        #         if j not in vistied:\n",
    "        #             len_edges-=1\n",
    "        #             dfs(j)\n",
    "        # dfs(0)\n",
    "\n",
    "        # return len(vistied)==n and len_edges==0\n",
    "\n",
    "        # neet code\n",
    "        if not n:\n",
    "            return True\n",
    "        adj={i:[] for i in range(n)}\n",
    "        for n1,n2 in edges:\n",
    "            adj[n1].append(n2)\n",
    "            adj[n2].append(n1)\n",
    "        visit=set()\n",
    "        def dfs(i,prev):\n",
    "            if i in visit:\n",
    "                return False\n",
    "            visit.add(i)\n",
    "            for j in adj[i]:\n",
    "                if j==prev:\n",
    "                    continue\n",
    "                if not dfs(j,i):\n",
    "                    return False\n",
    "            return True\n",
    "\n",
    "        return dfs(0,-1) and n==len(visit)    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validTree(self, n: int, edges: List[List[int]]) -> bool:\n",
    "        adj = defaultdict(list)\n",
    "        for a, b in edges:\n",
    "            adj[a].append(b)\n",
    "            adj[b].append(a)\n",
    "        \n",
    "        visited = set()\n",
    "\n",
    "        def dfs(node: int, parent: int):\n",
    "            if node in visited:\n",
    "                return False \n",
    "            visited.add(node)\n",
    "            for neighbor in adj[node]:\n",
    "                if neighbor != parent and not dfs(neighbor, node):\n",
    "                    return False\n",
    "            return True \n",
    "        \n",
    "        noCycle = dfs(0, -1)\n",
    "        return noCycle and len(visited) == n "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validTree(self, n: int, edges: List[List[int]]) -> bool:\n",
    "        graph = collections.defaultdict(list)\n",
    "        for a, b in edges:\n",
    "            graph[a].append(b)\n",
    "            graph[b].append(a)\n",
    "\n",
    "        visited = [0]*n\n",
    "        def dfs(i, p):\n",
    "            if visited[i]==1:\n",
    "                return False\n",
    "            \n",
    "            if visited[i]==2:\n",
    "                return True\n",
    "\n",
    "            visited[i] = 1\n",
    "            for nb in graph[i]:\n",
    "                if nb==p:\n",
    "                    continue\n",
    "\n",
    "                if not dfs(nb, i):\n",
    "                    return False\n",
    "            visited[i] = 2\n",
    "            return True\n",
    "\n",
    "        if not dfs(0, -1) or sum(visited) != 2*n:\n",
    "            return False\n",
    "        \n",
    "\n",
    "\n",
    "        return True\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validTree(self, n: int, edges: List[List[int]]) -> bool:\n",
    "        graph = defaultdict(list)\n",
    "        for a,b in edges:\n",
    "            graph[a].append(b)\n",
    "            graph[b].append(a)\n",
    "\n",
    "        visited = set()\n",
    "        \n",
    "        def dfs(node: int, parent: int) -> bool:\n",
    "            print(node)\n",
    "            if node in visited:\n",
    "                return False\n",
    "            visited.add(node)\n",
    "            \n",
    "            for neighbor in graph[node]:\n",
    "                #print(\"parent: \", node, \"node: \", neighbor)\n",
    "                if neighbor != parent and not dfs(neighbor, node):\n",
    "                    return False \n",
    "            return True \n",
    "        \n",
    "        return dfs(0, -1) and len(visited)==n\n",
    "            \n",
    "            \n",
    "            \n",
    " \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def validTree(self, n: int, edges: List[List[int]]) -> bool:\n",
    "        vertice_2_adjs = { i : set() for i in range(n)}\n",
    "        visited = [False for i in range(n)]\n",
    "        for edge in edges:\n",
    "            vertice_2_adjs[edge[0]].add(edge[1])\n",
    "            vertice_2_adjs[edge[1]].add(edge[0])\n",
    "\n",
    "        valid = self.dfs(visited, set(), None, 0, vertice_2_adjs)\n",
    "        if not valid:\n",
    "            return False\n",
    "        for vertice in vertice_2_adjs.keys():\n",
    "            if not visited[vertice]:\n",
    "                return False            \n",
    "        return True\n",
    "\n",
    "    def dfs(self, visited, path, pre_vertice, vertice, vertice_2_adjs):\n",
    "        visited[vertice] = True\n",
    "        adj_vertex = vertice_2_adjs[vertice]\n",
    "        for adj_vertice in adj_vertex:\n",
    "            if adj_vertice in path:\n",
    "                return False\n",
    "            if visited[adj_vertice]:\n",
    "                continue\n",
    "            path.add(pre_vertice)\n",
    "            valid = self.dfs(visited, path, vertice, adj_vertice, vertice_2_adjs)\n",
    "            path.remove(pre_vertice)\n",
    "            if not valid:\n",
    "                return False\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validTree(self, n: int, edges: List[List[int]]) -> bool:\n",
    "        if not n:\n",
    "            return True\n",
    "        adj = {i:[] for i in range(n)}\n",
    "        for n1, n2 in edges:\n",
    "            adj[n1].append(n2)\n",
    "            adj[n2].append(n1)\n",
    "        visited = set()\n",
    "        def dfs(i, prev):\n",
    "            if i in visited:\n",
    "                return False\n",
    "            visited.add(i)\n",
    "            for j in adj[i]:\n",
    "                if j==prev:\n",
    "                    continue\n",
    "                if not dfs(j, i):\n",
    "                    return False\n",
    "            return True\n",
    "        \n",
    "        return dfs(0,-1) and n == len(visited)\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
